The present invention relates generally to synchronization of data--that is, the process of taking two different stores of data ("data stores"), comparing them to identify differences, and applying changes to one or both to make them identical. More particularly, the present invention relates to a methodology for negotiating the synchronization process that is to occur among two or more computing devices, in a data-processing or computing environment.
With each passing day, there is ever increasing interest in providing synchronization solutions for connected computing devices, particularly information appliances. These "appliances" appear in the form of electronic devices including, but not limited to, cellular phones, pagers, other hand-held devices (e.g., REX.TM., PalmPilot.TM.and Windows.TM. CE devices), personal computers (PCs) of all types and sizes, and Internet or intranet access devices (e.g., PCs or embedded computers running, for example, Java virtual machines or browsers or Internet Protocol (IP) handlers).
These devices, and the software applications running on these devices, do not communicate particularly well with one another and are typically not designed with data synchronization in mind. Therefore, a problem exists as to how one integrates information --such as calendaring, scheduling, and contact information --among disparate devices and software applications. Consider, for instance, a user who has his or her appointments on a desktop PC at work, but also has a notebook computer at home, and a battery-powered, handheld device for use in the field. What the user really wants is for the information (e.g., appointments) in each device to remain synchronized with corresponding information in all devices in a convenient and transparent manner. Still further, some devices (e.g., PCs) are typically connected at least occasionally to a server computer (e.g., an Internet server which stores information for the user). The user would, of course, like the information on the server computer to participate in the synchronization so that the server also remains synchronized.
An early approach to maintaining consistency between data sets was to import or copy one data set on top of another. This simple "one-way" approach, which overwrites a target data set without any attempt at reconciling any differences, is inadequate for all but the simplest of applications. Not unexpectedly, more sophisticated synchronization techniques were developed. In particular, techniques were developed for synchronization of exactly two data sets by attempting to reproduce in each data set the changes found in the other data set since a previous synchronization. A detailed review of different synchronization techniques can be found in the Background section of commonly-owned application Ser. No. 08/923,612, filed Sep. 4, 1997, and entitled SYSTEM AND METHODS FOR SYNCHRONIZING INFORMATION AMONG DISPARATE DATASETS, the disclosure of which is hereby incorporated by reference in its entirety, including any appendices or attachments thereof, for all purposes.
Today, a variety of approaches exist for synchronizing information residing on multiple computing or information-storing devices. Consider, for instance, the task of synchronizing respective data sets or "data stores" residing on a given pair of devices. Here, the particular synchronization process employed depends on the capabilities of the individual devices. Consider, for instance, the following two examples:
Example 1: A synchronization or "sync" engine communicating with a fairly primitive device may have to obtain a complete copy of the data store from the device, do the comparison, and then re-write the entire data store back to the device. PA1 Example 2: The same sync engine, when communicating with a higher-level device, may be able to send a request to the other (target) device for all changes to the data store that were made after the last sync date. The target device will then transmit only those changes, reducing the amount of data that is transmitted and the time required for synchronization. PA1 1. Headers include a CRC (cyclic redundancy checking) value for each record. PA1 2. Headers include a modification time (time stamp) for each record. PA1 3. Headers include a change counter for each record. These three options are reflected in a "CHANGE_TRACKING" parameter, which indicates what the device's capabilities are in terms of knowing what has changed. This parameter may be set to one of the following values: EQU CHANGE_TRACKING={NONE.vertline.CRC.vertline.TIMESTAMP.vertline.CHANGE_COUNT ER } PA1 1. The device can only transmit and receive the entire data store as a block; it is not possible to request or submit individual records. PA1 2. The device provides "static index" access to the records (i.e., there are a fixed number of record storage "slots" and the sync engine can request and submit records based on this slot number. The records may move to different slots in between synchronizations, so there is no lasting fixed correlation between a slot number and a record). PA1 3. The device provides "unique IDs" for each record, and the sync engine can request and submit individual records using these IDs. Unique IDs are guaranteed to be unique within a particular data store, and the association between a record and its ID is never broken.
Each example will be reviewed in turn.
Example 1 indicates a primitive synchronization process, where a synchronization engine must communicate with a primitive device (e.g., one not including any native support for synchronization). In such a case, the synchronization engine must follow a resource-intensive (and typically slow) process. First, the synchronization engine requests the entire data store from the device and then proceeds to determine what differences exist in the data store by comparing it to a previously-stored copy of the data store. After applying any necessary changes (i.e., for creating a data store that is synchronized according to user-specified configuration), the synchronization engine must now transmit the entire copy back to the primitive device.
Example 2 indicates a higher-level synchronization process, in which the synchronization engine communicates with a device having at least some degree of support for synchronization. Support might include, for example, the ability of the device to transmit to the synchronization engine any new or modified records as of a certain date. Typically, the level of synchronization support is due in part to what is stored in the data store, the type of program functionality (i.e., software features) that is available, and the processing power that is available for the synchronization interface (to that device). Beyond the disparate levels of synchronization illustrated by the preceding examples, a variety of other possible levels exist, each one taking advantage of the features of a particular device to get the most efficient synchronization possible.
A problem exists with these present-day approaches, however. In order for two devices to synchronize together (i.e., participate in a synchronization session), they have to have some means of communication--that is, a "synchronization protocol". With existing solutions, however, a "hard-wired" protocol (i.e., one supporting only a particular device, such as a Palm Pilot device) is employed. As a result, the protocol employed is specific to the needs and features of a particular device, at the expense of not supporting other devices. From the perspective of the software developer, one creates a device-specific "accessor" (i.e., driver capable of accessing data) for a particular target device, with the requirement that the developer knows the particular synchronization capabilities of the target device beforehand. The problem with such an approach, however, is that the synchronization driver is tied to a specific device; it cannot be effectively re-used from one device to another. As the target device itself typically undergoes revision, the device-specific driver soon becomes obsolete, since it does not support newer versions of the very same device for which it was specifically designed.
Recently, some attempts have been made to create generalized synchronization protocols. However, instead of handling a variety of different device synchronization-support levels, these protocols assume some particular level of synchronization support, and only devices capable of that level of support can be synchronized. Here, such a protocol attempts to provide some degree of reuse by adopting a common denominator for target devices using that protocol. This approach is also problematic. Quite simply, if a device does not meet the common denominator, it is completely shut out from use of the protocol, despite the fact that the device may actually include some degree of built-in synchronization support (which could have been used to optimize synchronization). In other words, the approach has no capability to support those devices which, although not adhering completely to the specified protocol, have at least some intermediate level of synchronization support. Therefore, the approach is only an incremental improvement over the above-described single-device protocol.
What is needed are systems and methods that support a generalized synchronization protocol, yet do so in a manner which is adaptable to the capabilities of a particular target device. In such a case, the target device is not required to have a particular degree of synchronization support in order to use the protocol. Instead, the protocol allows the synchronization process to proceed in the most efficient manner possible, given the level of synchronization support provided by the target device, whatever level that might be. The present invention fulfills this and other needs.